1000 5000 140 621 243 726 587 733 74 55 132 638 706 554 864 491 694 797 834 85 859 260 177 834 243 165 273 617 388 714 498 272 726 298 256 167 409 328 769 386 597 299 179 963 375 701 355 45 3 780 927 442 756 803 597 718 198 594 674 985 69 722 324 57 659 994 503 318 366 869 620 357 960 889 78 158 877 882 963 813 728 829 609 660 958 141 358 856 929 185 79 295 599 76 738 905 281 204 131 804 628 972 747 6 891 138 405 95 691 457 135 4 277 936 735 941 144 545 763 352 525 435 136 68 49 784 780 326 414 984 164 168 178 437 214 213 951 189 680 415 593 667 200 945 531 157 905 12 482 119 701 286 601 599 357 463 555 503 538 762 948 159 864 18 65 80 198 987 347 714 607 100 664 822 20 252 665 309 88 410 485 959 354 883 13 477 855 824 598 832 645 189 114 247 657 899 735 54 418 382 47 89 763 320 966 108 157 965 743 215 187 629 432 162 20 94 201 197 93 255 905 603 76 989 497 722 390 362 598 573 874 585 547 643 203 595 581 653 594 933 934 283 810 927 891 239 594 863 893 976 303 156 12 129 159 20 631 864 375 7 565 559 342 185 352 326 560 611 108 879 715 195 716 209 685 135 438 590 253 14 834 421 877 168 463 945 287 17 102 559 293 98 397 940 950 655 669 828 120 538 916 92 617 15 491 114 245 46 417 8 603 492 751 84 408 98 275 411 962 20 141 449 94 107 956 42 523 820 522 397 589 719 723 123 339 249 323 165 281 434 509 363 286 248 445 526 535 410 406 599 162 174 44 469 276 539 700 443 364 455 527 239 662 907 779 869 329 930 154 66 569 381 233 465 965 922 818 881 474 321 394 637 399 157 460 851 94 113 612 414 305 617 837 444 619 436 692 984 851 329 98 105 261 254 989 521 577 818 848 535 169 117 551 422 823 67 92 476 925 485 437 403 467 544 891 27 869 484 820 950 66 6 330 515 430 254 402 516 256 113 854 392 21 376 771 489 356 224 764 38 80 744 877 43 681 238 889 252 171 258 181 958 717 521 498 759 979 980 991 432 188 814 220 834 429 145 544 966 29 722 828 835 175 665 494 141 251 706 863 736 453 350 438 601 836 27 370 901 932 279 388 895 132 273 859 823 745 113 997 750 882 419 285 507 170 800 223 793 769 828 494 502 299 217 839 245 815 850 883 573 369 930 985 64 577 315 793 326 370 631 674 783 539 818 662 164 25 573 161 799 420 325 509 750 293 74 280 372 455 609 564 896 491 10 126 924 585 594 704 663 238 738 472 683 449 831 783 456 533 8 938 263 386 716 236 40 180 505 602 53 906 341 709 509 665 833 84 505 574 176 208 570 167 725 878 89 291 786 1000 670 885 2 836 522 149 185 115 685 319 846 460 1000 34 896 439 876 627 293 554 561 607 52 335 240 788 397 76 722 873 540 314 502 577 634 550 903 181 740 347 828 750 738 702 814 399 312 512 589 921 481 224 484 461 887 759 56 398 444 858 365 636 420 483 17 922 328 705 214 784 205 731 29 298 876 448 622 807 624 226 873 516 754 607 312 318 968 567 458 627 577 49 666 858 282 870 853 358 989 171 320 968 637 179 312 418 948 955 24 996 381 341 375 546 250 462 735 244 238 911 758 61 356 727 233 157 863 232 180 79 992 342 612 268 459 243 701 342 66 414 148 829 632 743 143 446 167 821 615 886 772 576 165 811 541 967 714 164 610 626 230 165 465 681 778 332 256 428 629 470 863 9 595 459 866 370 769 653 524 732 987 613 87 481 878 926 5 542 302 968 83 941 881 878 72 164 266 233 626 885 247 859 913 413 668 332 306 165 478 832 158 475 192 839 257 2 97 573 323 477 772 199 138 408 959 764 430 192 653 977 859 158 164 731 210 920 79 370 385 64 509 472 31 683 152 222 513 291 911 799 655 653 604 11 103 732 39 374 425 628 441 278 786 760 50 728 682 380 844 428 21 723 550 956 806 571 18 585 567 76 926 487 290 981 983 612 243 383 713 908 555 584 264 432 527 889 995 666 143 856 332 666 776 543 553 653 267 539 14 297 835 102 288 218 746 294 747 744 301 299 966 567 12 860 106 685 795 523 78 183 987 197 422 61 745 235 151 113 430 460 236 4 262 96 140 34 65 430 258 449 485 839 924 189 642 617 293 511 997 149 91 329 853 465 426 644 489 679 407 474 848 892 429 364 847 322 395 110 831 455 996 406 412 764 221 976 927 262 987 157 141 336 827 743 614 798 240 807 214 820 129 119 416 69 632 912 182 757 660 734 906 688 559 239 648 128 857 303 826 939 931 743 643 226 893 953 372 684 985 350 602 592 149 945 94 855 413 361 803 360 903 834 524 961 141 988 635 765 654 371 475 176 461 102 151 85 497 944 769 833 675 842 860 173 100 798 722 408 524 837 831 699 388 699 724 115 565 334 117 370 422 75 603 70 90 64 666 648 247 651 372 447 737 257 669 979 397 528 909 362 590 230 561 390 11 144 554 981 263 844 940 887 400 95 576 612 385 399 611 356 760 538 589 181 528 638 651 416 320 206 614 876 186 539 233 578 165 337 774 935 651 670 266 317 940 559 412 714 266 291 627 823 179 597 293 811 649 774 840 14 229 921 501 526 928 549 144 285 929 38 953 985 922 557 118 363 731 787 15 552 309 634 80 667 408 293 875 241 173 650 499 244 173 863 762 297 216 546 588 553 151 472 378 204 315 7 296 497 251 396 695 575 426 486 900 391 535 80 919 480 987 11 133 458 975 122 774 587 563 492 983 758 319 166 801 318 78 238 545 367 494 633 582 830 786 566 222 548 56 960 353 895 988 768 484 600 683 129 200 198 296 442 448 690 650 160 567 985 876 697 535 86 332 466 235 765 660 234 454 584 932 925 634 566 358 610 698 135 945 604 872 354 463 589 992 911 751 630 186 573 531 241 420 717 3 504 190 196 496 723 309 765 962 901 873 613 875 927 750 710 346 340 526 925 336 163 965 508 406 97 652 208 533 909 1000 316 437 1 240 932 159 343 82 522 931 650 934 5 82 985 88 917 117 648 355 65 892 6 785 865 944 256 12 972 770 324 481 411 697 511 688 892 400 864 717 600 101 867 161 685 340 943 209 341 306 320 486 589 530 61 339 359 499 339 667 168 728 761 73 235 543 114 614 652 139 294 390 22 666 256 547 677 247 777 792 100 385 260 183 9 226 41 452 492 689 99 544 396 769 73 927 674 256 480 802 724 1000 343 757 819 193 802 306 814 701 344 173 132 291 717 574 838 557 305 123 826 185 710 163 441 428 478 899 787 602 923 620 221 616 485 707 314 698 32 144 230 173 155 848 557 671 722 620 122 553 508 711 329 604 926 628 494 777 423 725 99 639 818 29 470 489 791 823 416 622 818 869 935 743 658 498 261 37 171 984 375 560 13 395 143 617 674 163 211 360 124 678 611 711 597 108 695 965 37 874 39 52 208 527 64 4 5 154 646 517 504 162 52 249 937 68 654 303 723 585 608 658 261 669 444 464 813 753 936 492 632 866 446 948 611 456 162 555 877 208 599 216 562 458 314 677 178 604 893 873 55 757 702 438 515 378 653 772 544 221 418 988 942 393 141 398 841 239 4 292 553 980 824 901 784 657 968 754 86 722 588 44 312 263 211 188 453 134 943 930 576 759 828 847 89 926 28 307 540 685 373 223 529 271 265 620 66 190 766 466 560 774 308 210 549 616 681 37 995 968 960 578 876 215 686 292 137 465 612 761 164 368 400 357 501 760 35 253 80 369 572 268 485 408 956 34 695 982 472 640 886 264 466 653 53 21 968 947 332 75 444 435 535 226 506 357 965 295 901 329 259 330 490 137 687 513 972 372 805 411 782 597 452 878 764 153 362 713 19 965 740 291 740 526 55 354 949 287 666 100 919 959 506 618 921 935 356 736 980 64 158 950 213 796 319 906 903 72 763 84 526 97 72 409 460 59 187 632 152 43 531 432 682 959 141 896 488 528 87 21 292 23 869 464 68 317 167 845 241 994 928 445 657 383 744 429 645 947 155 461 123 458 57 330 476 97 948 660 127 660 765 496 69 680 935 304 836 513 746 974 716 213 761 628 740 95 885 823 430 149 248 56 766 427 226 2 247 302 536 862 287 961 576 570 446 891 750 389 771 519 970 429 151 835 167 898 352 273 677 488 143 698 345 1 34 190 776 648 699 285 807 351 719 945 526 658 455 801 313 306 347 399 638 307 666 331 105 502 596 494 658 359 48 88 22 456 942 411 338 493 774 974 140 134 231 882 858 824 305 424 144 508 883 698 494 646 550 933 367 752 224 85 124 205 290 105 855 294 442 979 528 24 178 601 260 59 807 751 345 133 259 914 115 453 267 950 226 592 274 634 970 200 924 263 905 320 668 188 900 922 670 788 99 873 902 287 777 206 199 717 461 343 813 350 339 76 52 821 627 825 430 784 760 447 737 834 427 602 614 481 742 492 347 793 666 600 778 374 185 352 680 758 268 408 351 581 631 361 533 78 32 903 602 145 699 451 246 72 401 394 928 601 660 708 776 767 389 646 806 393 270 344 361 737 433 503 554 925 511 4 854 618 537 396 615 125 403 62 419 608 299 232 755 211 415 203 565 952 300 866 219 917 224 134 402 574 129 221 908 528 267 758 615 336 998 975 116 482 118 408 728 890 426 5 182 871 581 903 371 186 792 652 248 780 549 627 76 77 838 272 399 710 596 966 296 768 864 560 809 626 582 919 326 551 733 248 945 725 808 450 328 951 72 92 189 556 255 133 550 639 326 714 515 493 81 140 266 810 294 952 222 492 866 29 612 37 684 897 484 502 255 948 982 727 892 219 107 832 669 910 568 299 900 851 294 375 946 809 132 54 24 413 356 720 530 457 626 983 895 488 536 288 330 499 108 936 44 480 400 661 280 789 178 977 445 913 994 323 951 539 727 109 271 681 737 663 590 811 592 10 294 86 596 989 82 569 899 116 337 547 550 165 398 563 484 481 91 206 702 945 673 852 889 334 889 204 784 439 71 580 967 399 138 457 168 693 38 613 306 458 617 868 725 326 49 774 351 28 13 321 570 921 519 268 932 33 864 484 198 682 988 194 789 7 250 307 748 534 126 208 288 499 230 244 579 859 432 560 938 185 51 74 151 804 833 537 983 623 932 259 268 391 901 143 517 1 990 820 17 194 162 984 336 429 736 121 106 633 100 176 53 168 325 9 420 25 664 357 994 478 251 208 59 863 651 443 724 293 487 410 526 808 610 767 567 962 813 638 601 706 243 399 41 137 252 711 697 440 122 535 630 368 735 779 450 377 845 228 868 52 212 847 723 1 815 532 599 577 975 368 648 892 951 307 580 485 895 539 774 482 385 767 26 189 775 940 146 53 507 692 867 189 413 658 337 315 888 567 671 347 845 697 255 730 471 982 960 659 918 437 507 237 900 165 430 355 699 964 737 883 189 738 68 928 98 203 638 544 998 41 687 46 224 823 7 793 836 967 757 355 729 53 161 963 612 474 498 60 787 530 217 275 91 974 332 893 675 187 356 247 607 761 479 220 142 260 487 195 116 575 649 661 169 868 231 867 863 453 191 903 656 726 769 526 166 297 117 717 105 857 226 32 173 127 768 516 705 976 343 462 809 116 982 274 589 113 101 438 703 438 699 484 873 529 98 683 805 961 285 614 915 621 457 340 519 539 569 598 232 889 112 301 522 80 915 697 941 324 628 530 67 542 328 99 886 914 666 330 600 864 950 970 529 367 607 546 221 342 778 123 771 969 312 645 751 426 904 618 521 149 891 401 412 99 390 709 736 497 955 588 232 790 320 425 660 624 582 266 336 111 355 450 411 959 537 488 689 531 54 494 50 653 338 435 977 279 187 553 509 78 252 448 955 465 681 777 955 518 653 876 550 894 309 891 303 596 75 652 479 105 227 67 591 307 993 766 273 954 625 823 367 809 669 550 787 83 603 772 254 523 317 993 866 795 831 806 311 30 404 956 905 62 761 555 968 175 537 836 239 698 7 296 405 779 391 246 344 955 781 513 85 639 540 815 449 95 353 28 531 823 286 45 463 649 472 349 197 786 760 492 864 849 933 450 64 315 177 472 992 921 608 976 696 984 356 784 412 904 996 452 876 302 480 145 402 939 158 434 871 970 864 406 262 934 420 527 623 449 443 637 941 62 418 730 504 216 500 860 740 624 198 910 568 796 226 902 345 250 165 608 229 913 889 546 360 465 11 663 465 158 69 324 846 625 85 822 868 686 877 481 136 239 201 530 754 919 524 903 4 192 476 857 335 486 265 57 158 482 426 920 225 824 168 709 267 690 416 460 972 106 525 209 944 563 548 681 175 537 487 609 411 652 131 340 965 586 498 370 584 754 745 316 452 249 627 369 812 809 100 396 761 61 174 707 221 526 144 130 48 905 234 662 175 367 883 330 712 332 555 341 159 144 145 266 668 873 622 303 914 814 711 726 426 798 791 655 830 119 52 69 294 656 293 476 487 759 362 745 823 251 820 578 522 108 297 962 552 846 561 39 948 202 171 19 319 437 1 70 595 383 584 802 232 404 553 222 27 30 850 219 354 354 22 402 729 463 97 412 608 970 853 393 170 572 415 378 448 386 123 927 916 308 108 754 735 247 180 833 571 67 91 320 673 342 847 604 708 431 497 689 404 684 384 717 309 300 772 659 709 886 420 10 26 360 168 635 657 976 296 15 968 607 723 854 197 873 905 504 516 470 161 152 269 372 749 828 444 51 408 207 927 887 919 583 203 282 541 695 384 152 429 934 473 249 668 743 757 418 812 711 432 219 690 105 946 371 169 485 183 488 837 989 637 503 361 319 625 130 10 238 491 229 697 713 54 72 973 82 1 505 958 79 928 719 99 213 763 119 237 632 902 923 450 117 671 862 772 825 748 361 647 454 770 697 982 813 671 391 558 975 297 86 889 810 516 553 757 835 705 234 18 902 977 372 888 151 742 898 766 133 626 134 756 465 318 187 107 876 109 99 119 694 294 570 764 512 77 769 734 507 858 339 975 654 489 859 365 844 857 509 498 915 69 857 234 878 942 491 304 132 686 982 521 984 415 140 663 863 890 879 808 301 440 939 285 640 341 281 163 698 320 630 813 724 900 866 632 638 610 762 109 760 653 470 635 652 716 92 443 473 195 403 410 761 722 713 122 508 669 357 497 939 187 797 681 110 935 802 718 167 602 503 691 277 39 470 381 34 333 490 311 485 145 686 140 776 681 221 608 546 970 408 240 543 714 539 957 459 455 592 869 595 7 746 993 805 453 339 456 810 915 39 283 395 802 655 655 889 60 31 974 451 554 856 374 668 14 927 377 971 43 692 211 465 280 347 895 918 264 167 899 677 293 570 759 819 336 238 682 812 11 223 165 54 511 607 357 4 158 897 789 724 395 622 762 138 389 515 518 858 263 489 638 370 883 379 811 254 378 603 525 442 454 726 587 227 737 852 820 406 98 809 114 576 39 431 185 444 790 753 212 201 707 337 361 113 341 939 128 131 337 87 496 137 421 739 362 315 782 727 684 866 299 960 487 78 136 989 425 817 163 269 683 889 850 71 940 178 28 312 493 538 555 569 956 563 721 478 489 733 88 425 235 241 840 292 588 366 388 226 448 608 661 335 283 676 6 652 704 550 367 972 58 499 850 617 927 431 153 968 376 57 254 496 219 810 897 103 273 241 549 246 968 833 267 568 898 393 734 511 884 852 822 38 912 687 277 168 595 750 277 776 608 407 664 254 267 493 126 929 919 310 147 863 9 149 598 239 874 25 579 608 344 364 177 639 494 893 997 324 680 711 485 286 488 423 566 947 780 562 359 64 325 189 284 775 865 683 228 788 978 746 915 607 477 6 257 237 68 437 65 895 20 914 818 530 656 866 345 653 796 825 125 278 515 78 546 493 386 803 183 487 34 614 64 645 682 699 949 962 250 752 120 345 809 191 251 252 232 319 600 926 829 443 263 866 697 2 804 482 459 45 38 489 98 980 273 209 63 74 93 165 777 692 741 248 702 606 168 125 449 902 771 597 990 983 781 540 16 696 874 76 516 242 1 993 763 365 575 491 540 875 865 855 791 923 277 710 483 528 674 244 426 72 763 218 432 422 88 653 383 472 165 917 629 881 873 511 668 351 40 691 809 375 682 791 622 708 538 898 577 380 735 753 395 596 535 102 729 806 727 916 422 186 900 284 871 202 165 955 53 820 342 410 679 388 319 748 62 608 931 916 119 762 745 285 300 586 167 31 163 761 234 625 93 158 775 521 313 333 557 358 95 475 856 615 133 532 728 313 197 406 512 340 237 915 744 390 726 506 155 551 485 206 25 316 725 581 374 973 563 235 25 631 672 485 366 18 211 670 261 435 53 70 441 635 883 29 530 342 615 884 635 270 439 69 229 518 757 430 569 679 389 315 18 286 786 376 425 763 610 795 455 468 725 272 183 16 546 938 257 589 201 305 864 442 602 679 492 765 925 82 889 223 760 301 631 467 493 494 992 43 960 521 381 827 821 916 969 947 888 66 844 329 604 760 217 965 429 610 656 819 901 383 493 997 507 553 904 383 327 726 211 521 479 74 575 632 614 803 551 597 688 651 443 780 878 249 542 270 960 368 601 464 838 535 142 762 230 848 813 361 458 769 218 213 687 317 333 123 951 772 337 300 607 655 390 269 265 117 976 21 11 761 453 746 583 153 298 93 658 368 159 553 181 261 214 439 86 403 432 597 688 911 848 402 598 493 478 292 52 955 829 707 263 595 166 147 696 789 955 390 557 484 148 639 792 28 278 504 734 610 343 525 849 244 779 239 382 829 986 538 592 107 191 703 299 376 739 426 330 940 576 637 305 905 590 828 291 653 898 15 78 620 610 795 114 268 954 513 566 487 242 325 651 213 318 17 623 735 124 423 619 637 385 651 261 472 637 622 911 657 514 876 750 720 705 767 868 774 709 562 39 196 335 927 223 161 224 969 227 64 914 131 429 664 23 950 978 74 911 288 651 158 143 807 623 407 869 906 662 722 333 961 943 75 839 255 27 232 759 279 920 52 59 621 247 749 897 168 582 958 390 391 215 502 872 769 615 200 469 107 704 441 465 174 928 668 788 582 695 953 418 204 389 322 921 117 818 925 287 881 555 605 289 77 316 984 717 601 600 258 505 954 795 889 217 473 425 576 277 51 588 732 513 583 266 922 268 403 988 918 721 79 97 669 761 680 472 357 462 855 498 496 281 456 478 36 462 35 978 509 107 526 57 506 236 904 7 652 874 296 551 283 183 692 686 104 308 699 45 563 604 427 947 783 334 139 737 201 718 491 252 189 604 503 278 42 916 424 189 433 565 450 658 993 970 591 44 397 740 275 147 892 926 454 45 569 551 13 420 177 107 889 430 152 50 134 483 796 624 566 499 191 588 275 982 65 953 881 770 373 848 281 896 103 804 423 487 69 292 605 615 691 780 918 768 236 293 988 25 888 208 826 977 904 831 19 81 820 589 432 408 990 88 326 766 309 910 6 369 387 213 980 115 710 570 928 218 35 203 680 847 254 517 684 671 140 415 208 573 641 932 118 862 786 909 921 396 860 141 563 212 971 907 376 63 325 515 785 676 212 926 66 125 183 742 932 334 353 882 76 785 137 744 274 197 416 926 211 202 814 703 591 998 446 29 91 436 429 201 360 687 303 677 707 35 786 378 643 301 529 826 166 622 570 304 132 492 720 67 170 184 274 847 809 945 739 531 957 904 648 564 54 914 260 728 346 810 63 916 360 140 819 839 534 642 670 20 149 347 531 364 360 223 953 714 297 453 66 117 316 501 181 938 682 310 332 647 247 569 775 617 635 603 735 47 189 55 700 533 132 538 264 266 876 494 313 266 831 624 51 332 418 546 348 93 108 537 470 939 618 488 913 675 837 331 670 692 418 884 388 66 249 610 407 811 279 645 588 997 84 380 623 703 854 599 405 667 564 141 386 819 379 975 421 937 925 587 903 429 997 50 55 907 20 114 912 386 183 677 825 341 663 360 997 718 856 749 793 759 498 249 625 199 563 975 115 307 803 19 586 322 102 400 964 400 726 818 844 28 398 468 441 666 48 484 205 849 728 258 535 254 911 349 666 240 17 894 163 746 543 187 703 676 446 317 843 601 886 99 42 242 827 372 482 650 439 856 591 337 879 336 127 730 434 162 637 212 901 502 390 276 578 260 174 961 379 236 12 199 132 315 626 949 743 685 542 895 797 933 956 13 260 887 186 410 579 407 666 149 184 327 83 99 978 981 104 427 792 602 552 17 808 428 204 652 296 757 76 136 961 994 515 237 47 301 382 822 106 156 825 914 720 367 122 55 241 638 468 490 450 449 965 575 315 389 665 160 936 294 501 742 179 783 372 489 296 716 797 246 472 601 243 364 255 32 740 694 503 151 426 332 362 383 334 810 51 215 80 799 446 471 455 911 420 941 31 306 200 107 870 739 668 223 511 770 173 857 104 458 770 153 667 547 225 799 800 353 362 568 49 955 755 936 348 725 282 507 5 807 462 562 570 996 206 868 469 644 968 835 38 714 12 99 222 438 174 70 444 612 56 106 988 787 69 689 643 207 967 289 157 120 666 466 39 713 847 954 246 370 154 788 774 310 948 741 907 781 673 518 3 403 355 909 618 95 414 787 341 670 130 503 591 957 532 546 943 122 925 913 144 748 114 422 712 86 186 471 578 809 555 766 556 135 605 39 889 912 421 229 24 80 564 437 396 623 413 658 906 976 194 927 941 587 344 512 621 955 447 162 460 240 51 782 192 318 149 578 404 573 346 663 806 575 867 596 266 293 956 186 766 682 118 846 468 974 477 866 844 812 105 613 639 668 993 182 405 954 852 717 288 110 54 90 678 994 705 267 243 39 49 450 613 760 863 437 94 717 711 493 205 393 706 880 341 45 325 583 805 443 288 816 550 915 928 332 289 601 397 82 534 749 341 835 6 674 175 316 938 80 264 40 641 947 858 939 902 545 112 192 719 15 987 427 911 197 120 31 453 597 192 842 308 608 542 660 193 945 989 308 312 984 687 619 23 856 815 367 352 130 640 977 811 952 164 143 842 883 542 251 764 701 104 714 947 679 70 77 390 444 465 492 696 884 437 526 591 546 291 443 741 559 456 146 466 661 219 339 368 469 227 110 501 705 567 90 853 322 452 639 846 283 659 172 274 628 601 818 985 865 493 383 100 488 965 492 291